package com.example.tencentTrain;

public class Leetcode62_UniquePaths {
    public static void main(String[] args) {
        System.out.println(new Solution().uniquePaths(3, 7));
    }

    static class Solution {
        public int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            if (m == 1 || n == 1) return 1;
            for (int i = 0; i < m; i++) {
                dp[i][0] = 1;
            }

            for (int j = 0; j < n; j++) {
                dp[0][j] = 1;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }

            return dp[m - 1][n - 1];

        }
    }
}
